Navigation devices that include GPS (Global Positioning System) signal reception and processing functionality are well known, and are widely employed in vehicle navigation systems. Typically, a navigation device uses an algorithm to compute an “optimal” route, such as the faster, shortest, most fuel efficient, etc, between an origin and a destination on a navigable network represented by a digital map.
The digital map (or mathematical graph, as it is sometimes known), in its simplest form, is effectively a database containing data representative of nodes, most commonly representative of road intersections, and lines between those nodes representing the roads between those intersections. In more detailed digital maps, lines may be divided into segments defined by a start node and end node. These nodes may be “real” in that they represent a road intersection at which a minimum of 3 lines or segments intersect, or they may be “artificial” in that they are provided as anchors for segments not being defined at one or both ends by a real node to provide, among other things, shape information for a particular stretch of road or a means of identifying the position along a road at which some characteristic of that road changes, e.g. a speed limit. The nodes and segments are further defined by various attributes which are again represented by data in the database. For example, each node will typically have geographical coordinates to define its real-world position, e.g. latitude and longitude. Nodes will also typically have manoeuvre data associated therewith, which indicate whether it is possible, at an intersection, to move from one road to another; while the segments will also have associated attributes such as the legal speed limit, etc.
The algorithm used to determine the optimum route may take into account historic, existing or predicted information relating to roads or traffic. An optimum route to a destination is commonly calculated using a deterministic routing algorithm, in which each segment is assigned a cost (which may be fixed or time-dependent) and in which various possible routes between an origin and the destination are explored, to determine a route that has a lowest total cost along all of its segments.
In order to generate accurate, time-dependent routes, some routing algorithms use data indicating an expected speed of travel along the segment at a plurality of different time periods; such data typically being associated with relevant segments of the digital map. This data, which is typically derived from position data collected from a plurality vehicles that have travelled the segment in the past, i.e. historic data, and can thus be thought of as time-dependent average speed, can thus be used to determine a speed at any time of the day that a vehicle is expected to travel along the segment. An average speed associated with an element can be determined according to the method described in WO 2009/053411 A1; the entire contents of which is incorporated by reference.
Routing algorithms may also make use of real-time traffic information, such as live positional data, to adjust the historic expected speed or time of travel for a segment to reflect a current speed or time or travel, and thus taking account of current events effecting movements along portions of the navigable network, e.g. traffic, weather, etc. Live data may be thought of as data which is relatively current and provides an indication of relatively current conditions on each navigable element. The live data may typically relate to the conditions on the elements within the last 30 minutes, 15 minutes, 10 minutes or 5 minutes.
However, routes generated by such deterministic routing algorithms are not always ideal where a user wishes to arrive at a destination by a particular time (e.g. in order to catch a specific train, or to attend a scheduled business meeting). A user may, for example, be led to expect to arrive at his destination by a particular time when following a fastest route, as computed at the start of his journey. However, such a route may be prone to unpredictable delays, such as queues due to congestion, accidents, road works, etc, which could cause the user to arrive later than the expected time. A route that is typically slower, but more consistent in the time taken to travel it, may have a greater likelihood of getting the user to his destination by the required time. Even if a user does not have to arrive at his destination by a particular time, he may still prefer a route that is, on average, a little slower over a route that is, on average, faster, if the slower route has less variation in the total journey time. There is thus a desire for navigation devices that can generate such routes.
Non-deterministic (stochastic) routing algorithms have been developed that can generate routing policies that maximise the probability of arriving at a destination within a predefined time budget. For example, the journal article “Optimal Routing for Maximizing the Travel Time Reliability” by Y. Fan and Y. Nie, Networks and Spatial Economics, volume 6:3-4, pp. 333-344, Springer 2006, the content of which is hereby incorporated by reference, describes a “Stochastic On-Time Arrival” (SOTA) algorithm that can generate such a routing policy. Rather than using single cost values for respective road segments, such an algorithm makes use of probability density or mass functions for respective road segments. These functions assign probabilities to a set of possible travel times for the segment.
The routing policy generated by such an algorithm is not a single route, but is instead defined by a set of nonlinear equations. The path of a journey based on such a routing policy will vary based on the actual time taken by the traveller to reach each particular node (which determines how much time remains from the predefined time budget to reach the destination). The equations therefore provide a dynamic routing strategy for travelling from the origin to the destination, which takes account of the actual time taken to travel between nodes to adapt the route as the journey progresses. When using a routing policy to navigate to a destination, a decision as to which path to take at an intersection is not determined in advance (as with deterministic algorithms), but is made as the user arrives at the intersection, based on his remaining time budget, so as to maximize the probability of arriving at the destination within the time budget. Accordingly, if a user has traversed a first leg of a journey faster than expected, then he may be instructed to take a possibly slower, but more reliable route, for the second leg. Conversely, if a user has traversed the first leg slower than anticipated, then he may be instructed to take a quicker, but more risky route, for the second leg.
For the sake of completeness, the SOTA model can be summarised in the following manner. Let us consider a directed network G(N,A) with |N|=n nodes and |A|=m links. The weight of each link (i,j)∈A is a random variable with probability density function pij(·) that represents the travel time on link (i,j). Given a time budget T, an optimal routing strategy is defined to be a policy that maximizes the probability of arriving at a destination node s within time T. A routing policy is an adaptive solution that determines the optimal path at each node in the network based on the travel time realized to that point. This is in contrast to a-priori solutions that determine the entire path prior to departure. Given a node i∈N and a time budget t, ui(t) denotes the probability of reaching node s from node i in less than time t when following the optimal policy. At each node i, the traveller should pick the link (i,j) that maximizes the probability of arriving on time at the destination. If j is the next node being visited after node i and ω is the time spent on link (i,j), the traveller starting at node i with a time budget t has a time budget of t-ω to travel from j to the destination, as described in the following equation:
                    u        i            ⁡              (        t        )              =                  max        j            ⁢                        ∫          0          t                ⁢                                            p              ij                        ⁡                          (              ω              )                                ⁢                                    u              j                        ⁡                          (                              t                -                ω                            )                                ⁢          d          ⁢                                          ⁢          ω          ⁢                                          ⁢          where                                ∀              i        ∈        N              ,          i      ≠      s        ,                  (                  i          ,          j                )            ∈      A        ,          0      ≤      t      ≤      T                          u        s            ⁡              (        t        )              =                  1        ⁢                                  ⁢        where        ⁢                                  ⁢        0            ≤      t      ≤      T      and pij(·) is the travel time distribution on link (i,j). The functions pij(·) are obtained, for example, using historic and/or live positional data, e.g. as described above with reference to determining average travel times. The functions pij(·) can be time-dependent, and can even include spatial and/or temporal correlations between links, e.g. as described in the journal article “A tractable class of algorithms for reliable routing in stochastic networks” by Samaranayake et al., Transportation Research Part C: Emerging Technologies, volume 20:1, pp. 199-217, Pergamon 2012; the content of which is hereby incorporated by reference.
While the generation of such routing policies has been studied at a theoretical level, it is not obvious how this theory can be exploited effectively in user-friendly navigation devices.